# 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
#
#  示例 1：
# 输入：nums = [1,2,3]
# 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
#
#  示例 2：
# 输入：nums = [0,1]
# 输出：[[0,1],[1,0]]
#
#  示例 3：
# 输入：nums = [1]
# 输出：[[1]]
from typing import List


class Solution:
    def permute2(self, nums: List[int]) -> List[List[int]]:
        """
        回溯写法二:去掉visited
        给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数
        假设已经填到第 first 个位置，那么 nums 数组中 [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合。
        我们肯定是尝试用 [first,n−1] 里的数去填第 first 个数，假设待填的数的下标为 i ，那么填完以后我们将第 i 个数和第first 个数交换，
        即能使得在填第 first+1个数的时候 nums 数组的[0,first] 部分为已填过的数，[first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作

        举个简单的例子，假设有 [2, 5, 8, 9, 10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8,9] 两个数，
        那么这个数组目前为 [8, 9 | 2, 5, 10] 这样的状态，分隔符区分了左右两个部分。假设这个位置要填 10 这个数，
        为了维护数组，将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10 | 2, 5]
        :param nums:
        :return:
        """
        res = []

        def backTrack(first: int) -> None:
            if first == len(nums):
                res.append(list(nums))
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                backTrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        backTrack(0)
        return res

    def permute1(self, nums: List[int]) -> List[List[int]]:
        """
        回溯写法一:
        使用set(visited)标记有哪些元素已经被添加到了当前结果集(singleRes)中
        :param nums:
        :return:
        """
        res = []

        def backTrack(visited: set, singleRes: List[int]) -> None:
            if len(singleRes) == len(nums):
                res.append(list(singleRes))
            for num in nums:
                if num not in visited:
                    visited.add(num)
                    singleRes.append(num)
                    backTrack(visited, singleRes)
                    singleRes.pop()
                    visited.discard(num)

        backTrack(set(), [])
        return res

    def permute(self, nums: List[int]) -> List[List[int]]:
        return self.permute2(nums)


if __name__ == "__main__":
    nums = [1, 2, 3]
    nums = [1, 2]
    print(Solution().permute(nums))
